package easy;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class Solution_1971 {

    public boolean validPath(int n, int[][] edges, int start, int end) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            Set<Integer> set_0 = map.getOrDefault(edge[0], new HashSet<>());
            set_0.add(edge[1]);
            map.put(edge[0], set_0);
            Set<Integer> set_1 = map.getOrDefault(edge[1], new HashSet<>());
            set_1.add(edge[0]);
            map.put(edge[1], set_1);
        }
        Set<Integer> covered = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        covered.add(start);
        while (!stack.empty()) {
            Integer pop = stack.pop();
            if (pop == end) {
                return true;
            }
            covered.add(pop);
            Set<Integer> integers = map.get(pop);
            if (integers != null) {
                for (Integer num : integers) {
                    if (!covered.contains(num)) {
                        stack.push(num);
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution_1971 model = new Solution_1971();
        System.out.println(model.validPath(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}, 0, 2));
        System.out.println(model.validPath(3, new int[][]{{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}}, 0, 5));
    }
}
